package q700_q800;

/**
 * Author: 笨蛋超人不会飞
 * Date:  15:14
 */
public class question_741 {

}
class Solution_741 {
    public int cherryPickup(int[][] grid) {
        int n=grid.length;
        int m=grid[0].length;
//        将grid里面的值重新赋值到一个新的二维数组里面
        int arr[][]=new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j]=grid[i][j];
            }
        }
//        第一步，先计算从起点到终点可以拿多少个
//        先走最后一列
        for (int i = n-2; i >=0 ; i--) {
            arr[i][m-1]=(arr[i+1][m-1]==-1||arr[i][m-1]==-1)?-1:arr[i][m-1]+arr[i+1][m-1];
        }
//        按照同样的方法给最后一行赋值
        for (int i = m-2; i >=0 ; i--) {
            arr[n-1][i]=(arr[n-1][i+1]==-1||arr[n-1][i]==-1)?-1:arr[n-1][i]+arr[n-1][i+1];
        }
//        接下来就是给arr矩阵剩下的元素赋值
        for (int i = n-2; i >=0 ; i--) {
            for (int j = m-2; j >=0 ; j--) {
                if(arr[i][j]==-1){
                    continue;
                }
                int a=arr[i+1][j];
                int b=arr[i][j+1];
                arr[i][j]=(a==-1&&b==-1)?-1:arr[i][j]+Math.max(a,b);
            }
        }

//      好了到这里就可以找到从头到终点的最多樱桃的数量了
//      先判断特殊情况
        if(arr[0][0]==-1){
//            说明走不到终点
            return 0;
        }
        int result=arr[0][0];
//        接下来更新原始的grid，之前走过的路樱桃值改为0,从起点到终点将下或者右中值较大的赋为0，并跳到这个点上，直到终点位置
        int s_index=0;
        int e_index=0;
        while (s_index!=n-1&&e_index!=m-1){
//          说明之前的路径中有这一步，所以就把樱桃数更新为0
            grid[s_index][e_index]=0;
            if(arr[s_index+1][e_index]>arr[s_index][e_index+1]){
                s_index++;
            }else{
                e_index++;
            }
        }
//        到这里说明走到了最后一行或者最后一列
        if(s_index==n-1) {
//            把后面的元素赋为0
            for (int i = e_index; i < m; i++) {
                grid[s_index][i] = 0;
            }
        }
        if(e_index==m-1){
//            把下面的元素赋为0
            for (int i = s_index; i < n; i++) {
                grid[i][e_index] = 0;
            }
        }
//      接下来按照最开始的方法重新对grid做一遍，不过起点变成了[n-1][m-1],终点变成了[0][0]
//        先走grid的第一列
        for (int i = 1; i <n ; i++) {
            grid[i][0]=(grid[i][0]==-1||grid[i-1][0]==-1)?-1:grid[i][0]+grid[i-1][0];
        }
//       再走第一行
        for (int i = 1; i <m ; i++) {
            grid[0][i]=(grid[0][i]==-1||grid[0][i-1]==-1)?-1:grid[0][i]+grid[0][i-1];
        }
//        接下来按照上面方法重新对grid做一遍，更新grid数组还没赋值的位置，不过起点变成了[n-1][m-1],终点变成了[0][0]
        for (int i = 1; i < n; i++) {
            for (int j = 1; j <m ; j++) {
                if(arr[i][j]==-1){
                    continue;
                }
//               将左边值给a
                int a=grid[i][j-1];
//               将上边值给b
                int b=grid[i-1][j];
                grid[i][j]=(a==-1&&b==-1)?-1:grid[i][j]+Math.max(a,b);
            }
        }
        return result+grid[n-1][m-1];
//

    }

    public static void main(String[] args) {
        //        grid =[[1,1,-1],[1,-1,1],[-1,1,1]]
        int grid[][]= {{1,1,-1},{1,-1,1},{-1,1,1}};
        Solution_741 s = new Solution_741();
        System.out.println(s.cherryPickup(grid));
    }


}
